#include <iostream>
#include <vector>
#include <gtest/gtest.h> 

using namespace std; 

class Solution
{
// time complexity O(n)
// space complexity O(n)
public:
int solve(int A) {

    int min_steps = 0;

    vector<int> turned_on(A);
    fill(turned_on.begin(), turned_on.end(), 0);

    for (int i = 0; i < A; ++i)
    {
        // skip the ones turned on already
        if (turned_on[i])
            continue;

        if (i + 2 < A && i + 4 < A)
        {
            turned_on[i] = 1;
            turned_on[i+2] = 1;
            turned_on[i+4] = 1;
        }
        else if (i - 2 >= 0 && i + 2 < A)
        {
            turned_on[i] = 1;
            turned_on[i-2] = 1;
            turned_on[i+2] = 1;
        }
        else if (i - 2 >= 0)
        {
            turned_on[i] = 1;
            turned_on[i-2] = 1;
        }
        else if (i + 2 < A)
        {
            turned_on[i] = 1;
            turned_on[i+2] = 1;
        }
        else
            turned_on[i] = 1;

        ++min_steps;
    }

    return min_steps;
}

};

TEST(TestSolution, SimpleTest)
{
    const int A = 13736; 
    Solution s; 
    EXPECT_EQ(s.solve(A), 4580) << "wrong answer"; 
}

int main()
{
    testing::InitGoogleTest();
    return RUN_ALL_TESTS();
}
